package top.humbleyuan.dp;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:18
 * @Des 解码方法
 */
public class LeetCode_91 {
    /**
     * 解码
     * 注：考虑"10","01"不同情况
     * 状态：d[i]表示到第i个字符为止有多少种方法
     * d[0] = 1,d[1] = s(0,1) > 26 ? 1 : 2
     * d[i] = d[i-1] + ( s(i-1,i) > 26 ? 0 : d[i-2])
     * 如果大于26，则方法数没有增加；
     * 若小于26：
     *      分开：d[i-1]种
     *      合并：d[i-2]种
     */
    public static void main(String[] args) {
        // 一般dp
        m1();

        // 依次循环
        m2();
    }

    public static void m1() {
        String s = "100";

        // 空串或0在开头
        if(s == null || s.length() == 0 || s.charAt(0) == '0') {
            System.out.println("有0种");
            return;
        }

        String newStr = "";
        int begin = 0;
        // 遍历一遍,检验将‘x0’形式的子串去掉
        for(int j = 1;j < s.length();j++) {
            if(s.charAt(j) == '0') {
                if(s.charAt(j-1) > '2' || s.charAt(j-1) == '0') {
                    System.out.println("有0种");
                    return;
                }
                else {
                    newStr += s.substring(begin,j-1);
                    begin = j+1;
                }
            }

        }
        newStr += s.substring(begin,s.length());
        int count = cal(newStr);
        System.out.println("共有"+ count + "种");
    }

    public static int cal(String s) {
        int[] d = new int[s.length()];
        if (s.length() == 0 || s.length() == 1 ) {
            return 1;
        }

        d[0] = 1;
        d[1] = Integer.valueOf(s.substring(0,2)) > 26 ? 1 : 2;
        for(int i = 2;i < s.length();i++) {
            d[i] = d[i-1] + (Integer.valueOf(s.substring(i-1,i+1)) > 26 ? 0 : d[i-2]);
        }
        return d[s.length()-1];
    }

    /**
     * 只是用一次循环
     */
    public static void m2() {
        String s = "227";

        // 空串或0在开头
        if(s == null || s.length() == 0 || s.charAt(0) == '0' ) {
            System.out.println("有0种");
            return;
        }
        if(s.length() == 1) {
            System.out.println("有1种");
            return;
        }
        if(s.charAt(1) == '0' && s.charAt(0) > '2' ) {
            System.out.println("有0种");
            return;
        }

        int[] d = new int[s.length()];
        d[0] = 1;
        d[1] = s.charAt(1) == '0' || Integer.valueOf(s.substring(0,2)) > 26 ? 1 : 2;
        for(int i = 2;i < s.length();i++) {
            if (s.charAt(i) == '0' ) {
                if(s.charAt(i-1) < '3' && s.charAt(i-1) > '0')
                    d[i] = d[i-2];
                else  {
                    System.out.println("有0种");
                    return;
                }
            } else {
                int val = Integer.valueOf(s.substring(i-1,i+1));
                d[i] = val > 26 ? d[i-1] : s.charAt(i-1) == '0' ? d[i-1] : (d[i-2] + d[i-1]);
            }

        }
        System.out.println("共有" + d[s.length()-1] + "种");
    }
}
